package com.lx.algorithm.heap;

import java.sql.Array;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

/**
 * Description: 手写堆
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-09-08 15:06:34
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-08     张李鑫                     1.0         1.0 Version
 */
public class MyHeap<T> {
    private List<T> heap;
    private Integer size;
    private HashMap<T, Integer> heapIndex;
    private Comparator<? super T> comp;

    public MyHeap(Comparator<? super T> comp) {
        this.comp = comp;
        heap = new ArrayList<>();
        size = 0;
        heapIndex = new HashMap<>();
    }

    /**
     * 给定一个整型数组，int[] arr；和一个布尔类型数组，boolean[] op
     * 两个数组一定等长，假设长度为N，arr[i]表示客户编号，op[i]表示客户操作
     * arr = [ 3   ,   3   ,   1   ,  2,      1,      2,      5…
     * op = [ T   ,   T,      T,     T,      F,      T,       F…
     * 依次表示：3用户购买了一件商品，3用户购买了一件商品，1用户购买了一件商品，2用户购买了一件商品，1用户退货了一件商品，2用户购买了一件商品，5用户退货了一件商品…
     * <p>
     * 一对arr[i]和op[i]就代表一个事件：
     * 用户号为arr[i]，op[i] == T就代表这个用户购买了一件商品
     * op[i] == F就代表这个用户退货了一件商品
     * 现在你作为电商平台负责人，你想在每一个事件到来的时候，
     * 都给购买次数最多的前K名用户颁奖。
     * 所以每个事件发生后，你都需要一个得奖名单（得奖区）。
     * <p>
     * 1，如果某个用户购买商品数为0，但是又发生了退货事件，
     * 则认为该事件无效，得奖名单和上一个事件发生后一致，例子中的5用户
     * 2，某用户发生购买商品事件，购买商品数+1，发生退货事件，购买商品数-1
     * 3，每次都是最多K个用户得奖，K也为传入的参数
     * 如果根据全部规则，得奖人数确实不够K个，那就以不够的情况输出结果gi
     * 返回当前堆的大小
     *
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 返回是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 返回堆顶元素
     *
     * @return
     */
    public T peek() {
        return heap.get(0);
    }

    /**
     * 在堆中放入一个元素
     */
    public void push(T obj) {
        heap.add(obj);
        heapIndex.put(obj,size);
        heapInsert(size++);
    }

    /**
     * 推出第一个元素
     *
     * @return
     */
    public T pop() {
        T t = heap.get(0);
        remove(t);
        return t;
    }

    /**
     * 移除一个元素
     *
     * @param obj
     */
    public void remove(T obj) {
        //首先获取待删除数的索引
        Integer integer = heapIndex.get(obj);
        //获取数组最后一个值
        T t = heap.get(--size);
        //移除索引记录表的记录
        heapIndex.remove(obj);
        //移除堆上最后一个值
        heap.remove(--size);
        //如果待移除的数不是最后一个数要重新排序
        if (obj!=t){
            //把最后一个值放到移除的索引上
            heap.set(integer,t);
            //设置新的索引
            heapIndex.put(t,integer);
            //重新排序
            resign(t);
        }
    }

    /**
     * 重新排序
     */
    public void resign(T obj) {
        heapInsert( heapIndex.get(obj));
        heapify( heapIndex.get(obj));

    }

    // 请返回堆上的所有元素
    public List<T> getAllElements() {
        return heap;
    }

    private void heapInsert(int index) {
        while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    // 任何比较器：
    // compare方法里，遵循一个统一的规范：
    // 返回负数的时候，认为第一个参数应该排在前面
    // 返回正数的时候，认为第二个参数应该排在前面
    // 返回0的时候，认为无所谓谁放前面
    private void heapify(int index) {
        int left = index * 2 + 1;
        while (left < size) {
            int best = left + 1 < size && comp.compare(heap.get(index + 1), heap.get(index)) > 0 ? index + 1 : index;
            best = comp.compare(heap.get(best), heap.get(index)) > 0 ? best : index;
            if (best == left) {
                break;
            }
            swap(index, best);
            index = best;
            left = index * 2 + 1;
        }
    }

    private void swap(int i, int j) {
        //获取两个值
        T t = heap.get(i);
        T t1 = heap.get(j);
        //交换两个数组的位置
        heap.set(j, t);
        heap.set(i, t1);
        //记录新的数索引所在的位置
        heapIndex.put(t, j);
        heapIndex.put(t1, i);

    }


}
